#include <string>
#include <iostream>
#include <vector>
#include "util.h"

#ifndef _COVER_H_
#define _COVER_H_

class Cover;
extern Cover * G_COVER;

/*
  returns an array a such that 
  a[-1] = 0
  a[i] = k * a[i-1] + s[i] (mod n)

  the hash of a substring 
     = s[begin .. end) = a[end-1] - a[begin-1] * k^(end-begin)
*/
#define kRollingHashK 29084723
#define kSearchHashBuckets 1000000

void IndexRollingHash(const string & s, vector<uint32> * ret);

// compute k^n mod 2^32
uint32 UInt32Pow(uint32 k, uint32 n);

uint32 ComputeRollingHash(const vector<uint32> &a, int begin, int end);

struct SubstringIndex {
  SubstringIndex(const string &s);
  void Search(const string & s, vector<uint32> * ret);

  string s_;
  vector<uint32> rolling_hash_;
  vector<vector<int> > hash_position_;
  // map<uint32, vector<int> > hash_position_;
};

// A cover covers a string using a number of elements from a set of solutions
// A solution represents a set of elements which are strings, generated by a program
// An element is a string generated by a program

struct Solution;

struct Element {
  string s_;
  Solution * solution_;
  int32 use_count_;

  string ToString();
  Element(const Element& e);
  Element(Solution * sol, string s);
};

struct Solution {
  vector<Element> elements_;
  int32  use_count_;
  double prior_ln_likelihood_;

  string ToString();
  Solution();

  void AddElement(string s);
};

struct Cover {
  // The cover may need to revert
  vector<pair<uint32, Element *> > added_;
  vector<pair<uint32, Element *> > removed_;
  vector<Solution *> solutions_removed_;

  map<uint32, Element *> elements_; // Start position -> element
  set<Solution*> solutions_;        // Currently used solutions
  SubstringIndex * si_;             // What we are trying to cover
  Solution * alphabet_;

  // Things we keep updated to compute the score easily
  double solution_ln_likelihood_;   // Sum of priors over all used solutions
  uint32 total_num_elements_;       // Number of referable elements
  double sum_ln_factorial_counts_;
  
  double Score(){
    return solution_ln_likelihood_
      + sum_ln_factorial_counts_
      + LnFactorial(total_num_elements_ - 1)
      - LnFactorial(total_num_elements_ - 1 + elements_.size());
  }

  void AddElementAt(uint32 pos, Element * e, bool add_change);

  void RemoveElementAt(uint32 pos, Element * e, bool add_change);

  Cover(SubstringIndex * si);

  // Try adding a solution, report back the improvement, difference?
  double TryAddSolution(Solution * s,
			vector<Solution *> * solutions_removed);

  void TryAddElement(Element * e);

  // The segment needs to replace at least 1 other segment to be viable
  void TryAddSegment(Element * e, uint32 pos);
};

void InitializeGlobalCover();

#endif
